package io.github.hadyang.leetcode.bytedance;

import java.util.concurrent.atomic.AtomicInteger;

/**
 * 最大子序和 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 *
 * <p>示例:
 *
 * <p>输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 进阶:
 *
 * <p>如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
 *
 * @author haoyang.shi
 */
public class Dynamic1029 {

  /**
   * 动态规划
   *
   * <p>用result[i]保存以数字nums[i]结尾的最大子序和，然后不断更新result数组的最大值即可。总的时间复杂度O(n)
   *
   * @param nums
   * @return
   */
  public int maxSubArray(int[] nums) {
    if (nums.length == 0) {
      return 0;
    }

    if (nums.length == 1) {
      return nums[0];
    }

    int[] res = new int[nums.length];
    res[0] = nums[0];

    int max = res[0];
    for (int i = 1; i < nums.length; i++) {
      int curMax = nums[i] + res[i - 1];
      if (curMax > nums[i]) {
        res[i] = curMax;
      } else {
        res[i] = nums[i];
      }
      max = Math.max(max, res[i]);
    }

    return max;
  }

  private int partition(int[] nums, AtomicInteger max, int start, int end) {
    if (start >= nums.length || start < 0 || end >= nums.length || end < 0) {
      return 0;
    }

    if (start == end) {
      return nums[start];
    }

    if (end - start == 1) {
      return nums[start] + nums[end];
    }

    int mid = (start + end) / 2;
    int rightRes = partition(nums, max, mid + 1, end);
    int leftRes = partition(nums, max, start, mid - 1);

    return 0;
  }

  public static void main(String[] args) {
    Dynamic1029 main = new Dynamic1029();
    System.out.println(main.maxSubArray(new int[] {-2, 1}));
    System.out.println(main.maxSubArray(new int[] {-1, -2}));
    System.out.println(main.maxSubArray(new int[] {-2, 1, -3, 4, -1, 2, 1, -5, 4}));
  }
}
